10167 - Birthday cake/10167.3.cpp

   1 /*
   2   Problem: 10167 - Birthday cake
   3   (From the UVa Online Judge)
   4   http://acm.uva.es/problemset/v101/10167.html
   5
   6   Divide-and-conquer solution
   7   (Read problem "10077 - The Stern-Brocot number system" for an idea about the divide-and-conquer argument)
   8   Basically I binary-search the perfect slope to cut the cake. It really isn't BINARY search, but every
   9   time the space of slopes that can possibly be a solution is reduced considerably.
  10
  11   Author: Andrés Mejía-Posada
  12   Date: May 6, 2008
  13
  14   This code gets Accepted in the online judge.
  15
  16  */
  17 #include <iostream>
  18 #include <vector>
  19 #include <algorithm>
  20
  21 using namespace std;
  22
  23 int n;
  24
  25 struct point{
  26   int x, y;
  27   point() {}
  28   point(const int &X, const int &Y) : x(X), y(Y) {}
  29 };
  30
  31 struct line{
  32   int a, b;
  33   line() {}
  34   line(const int &A, const int &B) : a(A), b(B) {}
  35 };
  36
  37 line operator |(const line &a, const line &b){
  38   line r;
  39   r.a = a.a + b.a;
  40   r.b = a.b + b.b;
  41   return r;
  42 }
  43
  44 //Returns positive if p is to the left of line l
  45 //Returns negative if p is to the right of line l
  46 //Returns zero if p is colineal with line l
  47 int cross(const point &p, const line &l){
  48   point q;
  49   q.x = l.b;
  50   q.y = -l.a;
  51
  52   return (p.x*q.y - q.x*p.y);
  53 }
  54
  55 //Returns positive if line l should rotate left
  56 //Returns negative if line l should rotate right
  57 //Returns zero if line l is a solution
  58 int check(const vector<point> &c, const line &l){
  59   int left = 0, right = 0;
  60   for (int i=0; i<2*n; ++i){
  61     int t = cross(c[i], l);
  62     left  += (t>0);
  63     right += (t<0);
  64   }
  65   if (left == right && left < n){ //2 or more points are colineal with the cut
  66     return -1; //? Or return 1? Does it matter? (It also gets accepted with +1, 0 will give a wrong answer though).
  67   }
  68   return (left - right);
  69 }
  70
  71
  72 int main(){
  73   while (scanf("%d", &n) && n){
  74     vector<point> cherry(2*n);
  75     for (int i=0; i<2*n; ++i){
  76       scanf("%d %d", &cherry[i].x, &cherry[i].y);
  77     }
  78
  79     line uphigh, upmed, updown, downhigh, downmed, downdown;
  80     uphigh = line(1, 0);
  81     if (check(cherry, uphigh) == 0){
  82       printf("%d %d\n", uphigh.a, uphigh.b);
  83       continue;
  84     }
  85     updown = line(0, 1);
  86     if (check(cherry, updown) == 0){
  87       printf("%d %d\n", updown.a, updown.b);
  88       continue;
  89     }
  90
  91     downhigh = line(0, 1);
  92     if (check(cherry, downhigh) == 0){
  93       printf("%d %d\n", downhigh.a, downhigh.b);
  94       continue;
  95     }
  96
  97     downdown = line(-1, 0);
  98     if (check(cherry, downdown) == 0){
  99       printf("%d %d\n", downdown.a, downdown.b);
 100       continue;
 101     }
 102
 103     while (true){
 104
 105
 106       upmed = uphigh | updown;
 107       int t = check(cherry, upmed);
 108       if (t == 0){
 109         printf("%d %d\n", upmed.a, upmed.b);
 110         break;
 111       }else if (t < 0){
 112         uphigh = upmed;
 113       }else{
 114         updown = upmed;
 115       }
 116
 117       downmed = downhigh | downdown;
 118       t = check(cherry, downmed);
 119       if (t == 0){
 120         printf("%d %d\n", downmed.a, downmed.b);
 121         break;
 122       }else if (t < 0){
 123         downhigh = downmed;
 124       }else{
 125         downdown = downmed;
 126       }
 127
 128     }
 129   }
 130
 131   return 0;
 132 }